<?php
/** 
* @file NTree.class.php
* @author kenlixin@gmail.com
* @version 0.1 design
* @date 2009-11-23
*/

class KD_QTree{
  
  /** 
  * @db and other setting: must be use ThinkPHP Model Class or adapter.
  * @param 'db'
  * @param 'table'
  * @param 'key'
  * @param 'left'
  * @param 'right'
  */
  private $_setting = array(
      'dsn'       =>  '',
      'dbType'  =>  'mysql',
      'host'        =>  'localhost',
      'user'      =>  'root',
      'psw'  =>  '',
      'table'     =>  'qtree',
      'key'       =>  'id',
      'left'      =>  'lft',
      'right'     =>  'rgt',
      'title'    =>  'title',   
  );
  
  private $dbType;
  
  public function __construct($setting = null,$dbType='mysql'){
    $this->dbType = $dbType;
    is_array($setting) && $this->_setting = array_merge($this->_setting, $setting);
  }
  
  public function insertRootNode($node){
    
    extract($this->_setting);

    $node = array(
      $left   => 1,
      $right  => 2,
    );

    KenDon::load('KD_Helper');
    $outArray = KD_Helper::arraySqlFormat($node, $dbType);
    //var_dump($outArray);

    $insertFields = implode(',', array_keys($outArray['output'][0]) );
    $insertValues = implode(',', array_values( $outArray['output'][0] ) );
    
    $sqlInsert = $this->dbType !==  'mysql' ?  
    "INSERT INTO `$table` ($insertFields) VALUES($insertValues);" : 
    "INSERT INTO $table ($insertFields) VALUES($insertValues);" ;
    
    //*
    $model = new KD_Model();
    try{
        $model->startTrans();
        $model->execute($sqlInsert);
        $model->commit();
        return true;
    }catch(Exception $e){   
        throw $e;
        return false;
    }
    //*/
  }
  
  public function init(){
    $virtual_root = array(
      $this->_setting['title'] => '#virtual_root#'
    );
    return $this->insertRootNode( $virtual_root );
  }

  public function isNode($node){
      extract($this->_setting);
      
      $result = isset($node[$key], $node[$left], $node[$right]) ? true : false;
      return $result;
      
  }
  
  public function getNode($key){

    extract($this->_setting);

    $sql    =   "SELECT * FROM `$table` WHERE `$key` = $key LIMIT 1;";
    
    $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);
      
    $m      =   new KD_Model();
    $record =   $m->query($sql);
    $result =   count($record)>0 ? $record[0] : null;

    return $result;
  } 
  
  public function getRootNode(){
    
    extract($this->_setting);
    
    $sql        =   "SELECT * FROM `$table` WHERE  `$right` = (SELECT MAX(`$right`) FROM `$table`);";
    
    $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);

    $model      =   new KD_Model();
    $record     =   $model->query($sql);
    $result     =   count($record)>0? $record[0]:null;
    
    return $result;
  }
  
  public function getRootNodes(){
    return $this->getICNodes( $this->getRootNode());
  }
  
  public function getParentNode($node){
  
  
    if($this->isNode($node) == false){ return null;}
    //($this->isNode($node) == false) && return null;

    extract($this->_setting);
    
    $node_lft   =   $node[$left];
    
    $node_rgt   =   $node[$right];

    $sql        =  "SELECT * FROM `$table` WHERE `$right`=(SELECT MIN(`$right`) FROM `{$table}` WHERE `$left`<$node_lft AND `$right`>$node_rgt ) ORDER BY {$left} ASC; ";
      
    $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);
      
    $model      =   new KD_Model();
    $record     =   $model->query($sql);
    $result     =   count($record)>0? $record[0] : null;

    return $result;
  }
  
  public function getNodePath($node){
    
    //$this->isNode($node) == false && return null;
    if($this->isNode($node) == false){return null;}

    extract($this->_setting);

    $node_lft   =   $node[$left];
    $node_rgt   =   $node[$right];

    $sql        =   "SELECT * FROM `$table` WHERE `$left`<$node_lft AND `$right`>$node_rgt;";
      
    $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);

    $model      =   new KD_Model();
    $record     =   $model->query($sql);
    $result     =   count($record)>0 ? $record : null;

    return $result;    
  }

  public function getAllNodes(){
      
      extract($this->_setting);

      $sql        =   "SELECT * FROM `$table` ORDER BY `$left` ASC;";

      $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);

      $model      =   new KD_Model();
      $record     =   $model->query($sql);
      $result     =   count($record)>0 ? $record : null;

      return $result;
  }  
  
  public function getSubNodes($node, $offset=0, $rows=5000){
      
    if($this->isNode($node) == false){return null;}
    //$this->isNode($node) == false && return null;

    extract($this->_setting);
       
    $node_lft   =   $node[$left];
    $node_rgt   =   $node[$right];

    $sql        =   "SELECT * FROM `$table` WHERE `$left` BETWEEN $node_lft AND $node_rgt ORDER BY `$left` ASC LIMIT $offset, $rows;";
      
    $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);
      
    $model      =   new KD_Model();
    $record     =   $model->query($sql);
    $result     =   count($record)>0 ? $record : null;
    
    return $result; 
  } 
  
  /** 第一子节点
  * 
  */
  public function getFCNode($node){
  
    if($this->isNode($node) == false){return null;}
    //$this->isNode($node) == false && return null;
    
    $record = $this->getSubNodes($node,0,2);
    
    $result = count($record)>1 ? $record[1] : null;
    
    return $result;
  }
  
  /** 同父同层节点 same level nodes
  *
  */
  public function getSLNodes($node){
  
    if($this->isNode($node) == false){return null;}
    //$this->isNode($node) == false && return null;
      
    extract($this->_setting);

    $parentNode = $this->getParentNode($node);
      
    if($this->isNode($parentNode) == false ){return $node;}
      
    $subNodes = $this->getSubNodes($parentNode); 
    array_shift($subNodes);
      
    $stack = $subNodes[0][$right];

    $result = array();
    foreach($subNodes as $item){
        if($item[$right]>=$stack){
            $stack=$item[$right];
            $result[]=$item;
        }
    }
    return $result;
  }
  
  /** 直接子节点 ImmediateChildNodes
  *
  */
  public function getICNodes($node){
    $fnode = self::getFCNode($node);
    //var_dump($fnode);
    $record = self::getSLNodes($fnode);
    //var_dump($record);
    $result = count($record)>0 ? $record : null;
    return $result;
  }
  
  public function displaySubTree($node){
      if($this->isNode($node == false)){return null;}

      extract($this->_setting);

      $result = array();
      $stack = array();

      $nodes = $this->getSubNodes($node); 
      
      foreach($nodes as $row){
          if(count($stack)>0){
              while($stack[count($stack)-1] < $row[$right]){
                  array_pop($stack);
              }
          }
          $result[] = str_repeat('--', count($stack)) . $row[$title];
          $stack[]    =   $row[$right];
      }
      
      return $result;
  }
  
  public function displayTree(){
      
      return $this->displaySubTree($this->getRootNode()); 
  }
  
  public function getChildCount($node){
      extract($this->_setting);
      return ( $node[$right] - $node[$left] - 1 )/2;
  }

  /** 
  * @brief insertNode class, default position is 'after'.
  * 
  * @param $targetNode
  * @param $referNode
  * @param $position after|before|below.
  * @return  true|false
  */
  public function insertNode($targetNode, $referNode, $position='after'){
      
      if(
        ($this->isNode($referNode) == false) &&
        in_array($position, array('after', 'before', 'below'))
      ){return false;}
      
      extract($this->_setting);
      
      if($position == 'after'){
        $updateLocalRefer = $referNode[$right];
        $insertRefer = $referNode[$right];
        
        //所有left>$referParentNode[right]的节点,left=left+2
        $sqlUpdateLeft  = "UPDATE `$table` SET `$left`=`$left`+2 WHERE `$left`>$updateLocalRefer;";
        
        //所有right>$referParentNode[right]的节点,right+right+2
        $sqlUpdateRight = "UPDATE `$table` SET `$right`=`$right`+2 WHERE `$right`>$updateLocalRefer;";
        
      }
      
      if($position == 'before'){
      
          $updateLocalRefer = $referNode[$left]-1;
          
          $insertRefer = $updateLocalRefer;
          
          $sqlUpdateLeft = "UPDATE `$table` SET `$left`=`$left`+2 WHERE `$left`>$updateLocalRefer;";
          
          $sqlUpdateRight = "UPDATE `$table` SET `$right`=`$right`+2 WHERE `$right`>$updateLocalRefer;";
      }
      
      if($position == 'below'){
           
          $updateLocalRefer = $referNode[$right]-1;
          
          $insertRefer = $updateLocalRefer;
          
          $sqlUpdateLeft      =   "UPDATE `$table` SET `$left`=`$left`+2 WHERE `$left`>$updateLocalRefer;";
          
          $sqlUpdateRight     =   "UPDATE `$table` SET `$right`=`$right`+2 WHERE `$right`>$updateLocalRefer;";

      }
      
      //echo $sqlUpdateLeft;
      //echo $sqlUpdateRight;
      
      $this->dbType !== 'mysql' &&
      $sqlUpdateLeft = KD_Helper::sqlFormat($sqlUpdateLeft) &&
      $sqlUpdateRight = KD_Helper::sqlFormat($sqlUpdateRight);
      
      //生成左右值
      $targetNode[$left] = $insertRefer+1;
      $targetNode[$right] = $insertRefer+2;
      
      //生成插入节点SQL
      KenDon::load('KD_Helper');
      $outArray = KD_Helper::arraySqlFormat(array($targetNode));
      //var_dump($outArray);

      $insertFields = implode(',', array_keys($outArray['output'][0]) );
      $insertValues = implode(',', array_values( $outArray['output'][0] ) );
      
      $sqlInsert = "INSERT INTO `$table` ($insertFields) VALUES($insertValues);";
      
      $this->dbType !== 'mysql' && $sqlInsert = KD_Helper::sqlFormat($sqlInsert);
      
      //*
      $model = new KD_Model();
      try{
          $model->startTrans();
          $model->execute($sqlUpdateLeft);
          $model->execute($sqlUpdateRight);
          $model->execute($sqlInsert);
          $model->commit();
          return true;
      }catch(Exception $e){   
          throw $e;
          return false;
      }
      //*/
  }

  public function deleteNode($node){
  
    if($this->isNode($node) == false){return null;}
    //$this->isNode($node) == false && return false; 
    
    extract($this->_setting);

    $nodeLeft       =   $node[$left];
    $nodeRight      =   $node[$right];
    $width          =   $nodeRight - $nodeLeft +1;

    $sqlDelete              = "DELETE FROM `$table` WHERE `$left` BETWEEN $nodeLeft AND $nodeRight;";
    //dump($sqlDelete);
    
    $sqlUpdateLeftValues    = "UPDATE `$table` SET `$right`=`$right`-$width WHERE `$right`>$nodeRight;";
    //dump($sqlUpdateLeftValues);
    
    $sqlUpdateRightValues   = "UPDATE `$table` SET `$left`=`$left`-$width WHERE `$left`>$nodeRight;";
    //dump($sqlUpdateRightValues); 

    $this->dbType !== 'mysql' &&
    
    $sqlDelete = KD_Helper::sqlFormat($sqlDelete) &&
    
    $sqlUpdateLeftValues = KD_Helper::sqlFormat($sqlUpdateLeftValues) &&
    
    $sqlUpdateRightValues = KD_Helper::sqlFormat($sqlUpdateRightValues) ;
    
    //*
    $model = new KD_Model();

    try{
        $model->startTrans();
        $model->execute($sqlDelete);
        $model->execute($sqlUpdateLeftValues);
        $model->execute($sqlUpdateRightValues);
        $model->commit();
        return true;
    }catch(Exception $e){
        throw $e;
        return false;
    }
    //*/
  }
  
  public function deleteAllNode(){
    extract($this->_setting);
    
    $sql ="DELETE FROM `$table`;";
    
    $this->dbType !== 'mysql' && $sql = KD_Helper::sqlFormat($sql);
    
    $model = new KD_Model();

    try{
        $model->execute($sql);
        return true;
    }catch(Exception $e){
        throw $e;
        return false;
    }
  }

  /** 
  * @brief 
  * 
  * @param $targetNode
  * @param $referNode
  * @param $position after|before|below
  * @return true|false. 
  */
  public function moveNode($targetNode, $referNode, $position='after'){}

}
